Option Strict On

' The following constant determine which one of the two models k-Mean or k-Center are we working on. This has two effect on the code:
' - How is the cost of the cluster calculated.
' - Which graph is analyzed.
#Const kMedian = True

Module NoNashValidation

    ' A representation of the graph. Each cell contain the distance on the edge between the two nodes represented by the corresponding row and column. A value of -1 represents a missing edge.
    ' A few places in the program assume that the graph is connected and the edge costs are not too large. More specifically, the edge costs should not add up to more than Integer.MaxValue \ 10.
    #If kMedian Then
        Private Graph(,) As Integer = New Integer(,) {{-1,  8, 10, -1, -1, -1, -1, -1, -1}, _
                                                      { 8, -1,  6,  4, -1, -1, -1, -1, -1}, _
                                                      {10,  6, -1,  7, -1, -1,  4,  7, -1}, _
                                                      {-1,  4,  7, -1, 10,  6, -1,  7, -1}, _
                                                      {-1, -1, -1, 10, -1,  8, -1, -1, -1}, _
                                                      {-1, -1, -1,  6,  8, -1, -1,  4, -1}, _
                                                      {-1, -1,  4, -1, -1, -1, -1,  6,  8}, _
                                                      {-1, -1,  7,  7, -1,  4,  6, -1, 10}, _
                                                      {-1, -1, -1, -1, -1, -1,  8, 10, -1}}
    #Else
        Private Graph(,) As Integer = New Integer(,) {{-1, 16, 18, -1, -1, -1, -1, -1, -1}, _
                                                      {16, -1,  9,  8, -1, -1, -1, -1, -1}, _
                                                      {18,  9, -1, 14, -1, -1,  8, 14, -1}, _
                                                      {-1,  8, 14, -1, 18,  9, -1, 14, -1}, _
                                                      {-1, -1, -1, 18, -1, 16, -1, -1, -1}, _
                                                      {-1, -1, -1,  9, 16, -1, -1,  8, -1}, _
                                                      {-1, -1,  8, -1, -1, -1, -1,  9, 16}, _
                                                      {-1, -1, 14, 14, -1,  8,  9, -1, 18}, _
                                                      {-1, -1, -1, -1, -1, -1, 16, 18, -1}}
    #End If


    ' The number of nodes in the graph.
    Private NumberOfNodes As Integer = Graph.GetLength(0)

    ' The distances between the nodes based on the information in Graph.
    Private Distances(,) As Integer = CalcDistances()

    ' This function calculates the distance between every two nodes on the graph. The function employs the Floyd–Warshall algorithm.
    Private Function CalcDistances() As Integer(,)
        ' Allocate space for the result array.
        Dim Distances(0 To NumberOfNodes - 1, 0 To NumberOfNodes - 1) As Integer

        ' Initialize the distance matrix according to the graph.
        For i As Integer = 0 To NumberOfNodes - 1
            For j As Integer = 0 To NumberOfNodes - 1
                If i = j Then
                    Distances(i, j) = 0
                Else If Graph(i, j) = -1 then
                    Distances(i, j) = Integer.MaxValue \ 10
                Else
                    Distances(i, j) = Graph(i, j)
                End If
            Next j
        Next i

        ' Perform edge relaxations to get the real distances.
        For k As Integer = 0 To NumberOfNodes - 1
            For i As Integer = 0 To NumberOfNodes - 1
                For j As Integer = 0 To NumberOfNodes - 1

                        If Distances(i, j) > Distances(i, k) + Distances(k, j)  Then
                            Distances(i, j) = Distances(i, k) + Distances(k, j)
                        End If

                Next j
            Next i
        Next k

        ' Return the distances calculated.
        Return Distances
    End Function

    ' A record representing a possible (centroid) half integral location on an edge.
    Private Structure Location
        ' One end node of the edge of the location.
        Dim Node1 As Integer
        ' The second end node of the edge of the location.
        Dim Node2 As Integer
        ' Twice distance from Node1 of the location. Since the distance must be half integral, this field is integral.
        Dim DoubleOffsetFromNode1 As Integer
    End Structure
   
   ' The entry point of the program.
    Public Sub Main()
        ' Check that the graph pass a few simple consistency tests.
        If Not CheckGraph() Then Exit sub

        ' This array represents a partition. Initially it represents a partition were all nodes are in one set (the FALSE set).
        Dim Partition(0 To NumberOfNodes - 1) As Boolean
        Call Array.Clear(Partition, 0, NumberOfNodes)

        ' Iterate over all the partitions
        Dim  FoundWeakEquilibrium As Boolean = False
        Do
            ' Find all the possible centeroid locations for both clusters under the current coloring
            Dim TrueCentroidLocations() As Location = FindPossibleCentoidLocations(Partition, True)
            Dim FalseCentroidLocations() As Location = FindPossibleCentoidLocations(Partition, False)

            ' Enumerate over all the possible centroid locations of the TRUE cluster, and check whether one of them is good enough to stop the nodes of this cluster
            ' from deviating (assuming the centroid of the FALSE cluster will move to the worst position from the deviating node's point of view).
            Dim TrueStable As Boolean = False
            For Each TrueCentroidLocation As Location In TrueCentroidLocations
                If IsStable(Partition, True, TrueCentroidLocation) Then
                    TrueStable = True
                    Exit For
                End If
            Next TrueCentroidLocation

            ' Enumerate over all the possible centroid locations of the TRUE cluster, and check whether one of them is good enough to stop the nodes of this cluster
            ' from deviating (assuming the centroid of the FALSE cluster will move to the worst position from the deviating node's point of view).
            Dim FalseStable As Boolean = False
            For Each FalseCentroidLocation As Location In FalseCentroidLocations
                If IsStable(Partition, False, FalseCentroidLocation) Then
                    FalseStable = True
                    Exit For
                End If
            Next FalseCentroidLocation

            ' If there is a choice of centroid locations that will make no node want to deviate, then we found a weak equilibrium.
            If TrueStable AndAlso FalseStable Then
                FoundWeakEquilibrium = True
            End If

            ' Advance to the next partition.
            Call NextPartition(Partition)

            ' Loop till we find a weak Nash equilibrium or get back to the original partition (where all the nodes were in the FALSE set).
        Loop Until FoundWeakEquilibrium OrElse Array.IndexOf(Partition, True) = -1

        ' Print the result
        If FoundWeakEquilibrium then
            Call Console.WriteLine("Found a weak Nash equilibrium.")
        Else
            Call Console.WriteLine("No weak Nash equilibria were found.")
        End If
    End Sub

    ' This function checks that the graph passes a few simple consistency tests, and prints an error message if it fails one of the tests.
    ' The function returns TRUE if and only if the graph pass all the tests.
    Private Function CheckGraph() As Boolean
        ' Check that the graph is given by a squre matrix.
        If Graph.GetLength(0) <> Graph.GetLength(1) Then
            Console.WriteLine("The graph is not given by a squre.")
            Return False
        End If

        ' Check that the graph is symmetric and contains no self loops.
        For i As Integer = 0 To NumberOfNodes - 1
            If Graph(i, i) <> -1 Then
                Console.WriteLine("A self loop was found in the graph.")
                Return False
            End If

            For j As Integer = 0 To i - 1
                If Graph(i, j) <> Graph(j, i) Then
                    Console.WriteLine("The graph is not given by a symmetric matrix.")
                    Return False
                End If
            Next j
        Next i

        ' If we got till here, then the graph passed all the checks.
        Return True
    End Function

    ' Given a partition and a cluster within this partition, this function finds all the possible locations for the centroid of this set.
    Private Function FindPossibleCentoidLocations(ByVal Partion() As Boolean, ByVal ClusterChosen As Boolean) As Location()

        ' We first find the lowest possible cluster cost. The following loops iterate over all possible half integral locations.
        Dim LowestDoubleClusterCost As Integer = Integer.MaxValue
        Dim CurrentCentroid As Location
        For i As Integer = 0 To NumberOfNodes - 1
            CurrentCentroid.Node1 = i
            For j As Integer = 0 To i - 1
                CurrentCentroid.Node2 = j
                If Graph(i, j) <> -1 Then
                    For k As Integer = 0 To 2 * Graph(i, j)
                        CurrentCentroid.DoubleOffsetFromNode1 = k

                        ' Calculate the cost of the cluster if the current centroid location is used.
                        Dim DoubleClusterCost As integer = CalcClusterCost(CurrentCentroid, Partion, ClusterChosen)

                        ' If the new cost is lower than the best cost seen so far, update the ebst cost
                        If DoubleClusterCost < LowestDoubleClusterCost Then LowestDoubleClusterCost = DoubleClusterCost

                    Next k
                End If
            Next j
        Next i

        ' Next, we iterate again over all the possible half integral locations, and keep only those which induce the optimal cluster cost calculated above.
        Dim BestLocations As New List(Of Location)
        For i As Integer = 0 To NumberOfNodes - 1
            CurrentCentroid.Node1 = i
            For j As Integer = 0 To i - 1
                CurrentCentroid.Node2 = j
                If Graph(i, j) <> -1 Then
                    For k As Integer = 0 To 2 * Graph(i, j)
                        CurrentCentroid.DoubleOffsetFromNode1 = k

                        ' Calculate the cost of the cluster if the current centroid location is used.
                        Dim DoubleClusterCost As integer = CalcClusterCost(CurrentCentroid, Partion, ClusterChosen)

                        ' If the new cost is lower than the best cost seen so far, update the ebst cost
                        If DoubleClusterCost = LowestDoubleClusterCost Then Call BestLocations.Add(CurrentCentroid)

                    Next k
                End If
            Next j
        Next i

        ' Return the list of optimal locations found
        Return BestLocations.ToArray()
    End Function

    ' This function gets a partition and a cluster inside the partition. It also gets a possible centroid location, and returns the cost of the cluster given this centroid location. 
    ' Remark: the function in fact returns twice the cost of the cluster. This guarantees that the resulting value is an integer.
    Private Function CalcClusterCost(ByVal Centroid As Location, ByVal Partion() As Boolean, ByVal ClusterChosen As Boolean) As Integer
        Dim DoubleClusterCost As Integer = 0
        For i As Integer = 0 To NumberOfNodes - 1
            If Partion(i) = ClusterChosen Then
                #If kMedian Then
                    DoubleClusterCost += CalcNodeCost(Centroid, i)
                #Else
                    DoubleClusterCost = Math.Max(DoubleClusterCost, CalcNodeCost(Centroid, i))
                #End If
            End If
        Next i
        Return DoubleClusterCost
    End Function

    ' This function gets a possible centroid location and an index of a node in the graph. The function returns the distance of the node from the centroid location.
    ' Remark: the function in fact returns twice the cost of the cluster. This guarantees that the resulting value is an integer.
    Private Function CalcNodeCost(ByVal Centroid As Location, ByVal Node As Integer) As Integer
        Return Math.Min(2 * Distances(Node, Centroid.Node1) + Centroid.DoubleOffsetFromNode1, _
                        2 * Distances(Node, Centroid.Node2) + 2 * Graph(Centroid.Node1, Centroid.Node2) - Centroid.DoubleOffsetFromNode1)
    End Function

    ' This function gets a partition and a cluster inside the partition. It also gets a possible centroid location, and checks whether any of the nodes of the cluster wish to deviate given this
    ' centroid location, assuming the centroid of the other cluster will move to the worst possible location from the point of view of the deviating node.
    Private Function IsStable(ByVal Partition() As Boolean, ByVal ClusterChosen As Boolean, ByVal Centroid As Location) As Boolean
        ' Check every node of the cluster.
        For i As Integer = 0 To NumberOfNodes - 1
            If Partition(i) = ClusterChosen Then

                ' Calculate the cost of the node currently pays.
                Dim OldDoubleCost As Integer = CalcNodeCost(Centroid, i)

                ' Determine the possible locations for the centroid of the cluster to which the node deviates.
                Dim NewPartition() As Boolean = DirectCast(Partition.Clone(), Boolean())
                NewPartition(i) = Not ClusterChosen
                Dim NewCentroids() As Location = FindPossibleCentoidLocations(NewPartition, Not ClusterChosen)

                ' Determine the distance of the node from the worst possible new centroid
                Dim LargestNewDoubleCost As Integer = 0
                For Each NewCentroid As Location In NewCentroids
                    Dim NewDoubleCost As Integer = CalcNodeCost(NewCentroid, i)
                    If NewDoubleCost > LargestNewDoubleCost then LargestNewDoubleCost = NewDoubleCost
                Next NewCentroid

                ' If the distance from the worst centroid is smaller than the distance from the current centroid, the node wishes to deviate.
                If OldDoubleCost > LargestNewDoubleCost Then Return False

            End If
        Next i

        ' If we got till here, no node wishes to deviate.
        Return True
    End Function

    ' This procedure gets a partition and replaces it in the next partition. The order between the partitions is defined by treating each partition as a value of a counter containing a bit
    ' for every node of the graph. This order gurantees we loop over all partitions before arriving back to the original partition.
    Private Sub NextPartition(ByVal Partition() As Boolean)
        Dim i As Integer = 0

        ' Set nodes to FALSE, till there are no more nodes or we reach a FALSE node.
        While i < NumberOfNodes AndAlso Partition(i)
            Partition(i) = False
            i += 1
        End While

        ' If we reached a FALSE node, make it TRUE.
        If i < NumberOfNodes Then
            Partition(i) = True
        End If
    End Sub

End Module